#ifndef TREE_GENERATION_H
#define TREE_GENERATION_H

#include <LADSUtil/tree.h>

#include "ComboReduct/combo/vertex.h"
#include "ComboReduct/combo/type_tree.h"
#include "ComboReduct/ant_combo_vocabulary/ant_combo_vocabulary.h"

namespace trees {

  using namespace ant_combo;

  template<int MIN_ARITY>
  class Generator {
  public:

    template<typename Selector>
    LADSUtil::tree<typename Selector::value_type> operator()(const Selector& sel,
							 int dp) const {
      typename Selector::value_type tmp;
      LADSUtil::tree<typename Selector::value_type> tr(tmp);
      build(sel,dp,tr,tr.begin());
      return tr;
    }

    template<typename Selector,typename T,typename iterator>
    void build(const Selector& sel,int dp,LADSUtil::tree<T>& tr,iterator it) const {
      if (dp==1) {
	tr.replace(it,sel.select(0));
      } else {
	int arity(sel.select_arity(MIN_ARITY));
	it=tr.replace(it,sel.select(arity));
	--dp;
	for (int i=0;i<arity;++i)
	  build(sel,dp,tr,tr.append_child(it));
      }
    }
  };

  typedef Generator<1> FullGenerator;
  typedef Generator<0> GrowGenerator;

  template<typename It,typename Selector>
  void ramped_half_and_half(It from,It to,const Selector& sel,
			    int minDp,int maxDp,bool type_check_enabled) {
    GrowGenerator gg;
    FullGenerator fg;
    bool gg_turn = true;
    bool well_typed;
    float ratio=((float)(maxDp-minDp+1))/(float)distance(from,to);
    for (It tr=from;tr!=to;) {
      (*tr)=(gg_turn?gg(sel,minDp+(int)(distance(from,tr)*ratio))
	     :fg(sel,minDp+(int)(distance(from,tr)*ratio)));
      well_typed = true;
      if(type_check_enabled) {
	std::stringstream strs;
	combo::vtree vtr;
	strs << (*tr);
	strs >> vtr;
	try {
	  combo::infer_type_tree(vtr);
	}
	catch(TypeCheckException) {
	  well_typed = false;
	}
      }
      if(well_typed) {
	++tr;
	gg_turn = !gg_turn;
      }
    }
  }

} //~namespace trees

#endif
